package com.jia.leetCode;

import java.util.Arrays;

/**
 * @program: Leetcode
 * @description:
 * @author: STU756
 * @create: 2020-08-09 14:58
 */
public class Pro5486 {
    public int minCost(int n, int[] cuts) {
        Arrays.sort(cuts);
        //dp[i][j]  第i个分割点和第j个分割点最小分割成本
        //dp[i][j], 设i < k < j, dp[i][j] = min(dp[i][k] + dp[k][j] + cuts[j] - cuts[i])

        int[] cu = new int[cuts.length + 2];
        System.arraycopy(cuts, 0, cu, 1, cuts.length);
        cu[0] = 0;
        cu[cu.length - 1] = n;

        int[][] dp = new int[cu.length][cu.length];
        dp[0][0] = 0;
        //初始化
        for(int i = 0; i < cu.length; i++) {
            for(int j = 0; j < cu.length; j++) {
                if(i == j && i == 0) {
                    dp[i][j] = 0;
                }else if(i == j - 1) {
                    dp[i][j] = 0;
                }else {
                    dp[i][j] = Integer.MAX_VALUE;
                }
            }
        }

        for(int i = cu.length -2; i >= 0; i--) {
            for(int j = i+1; j < cu.length; j++) {
                for(int k = i+1; k < j; k++) {
                    dp[i][j] = Math.min(dp[i][j], dp[k][j] + dp[i][k] + cu[j] - cu[i]);
                }
            }
        }
        return dp[0][cu.length - 1];

    }
}
